#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void getString(const string &digits, const vector<string> &table, string &curStr, vector<string> &ans,  int index)
{
   if (index == digits.size()) {
       ans.push_back(curStr);
       return;    
   }

   int digit = digits[index] - '0';
   for (int i = 0; i < table[digit].size(); i++) {         
        curStr[index] = table[digit][i];
        getString(digits, table, curStr, ans, index+1);
   }
}

class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> ans;
            vector<string> table(10);
            string curStr(digits.size(), 'a');
            table[2] = "abc";
            table[3] = "def";
            table[4] = "ghi";
            table[5] = "jkl";
            table[6] = "mno";
            table[7] = "pqrs";
            table[8] = "tuv";
            table[9] = "wxyz";
            getString(digits, table, curStr, ans, 0);
            return ans;
        }
};

//test in 1337 online test and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;    

    cout << "-----------------Test 1--------------------" << endl;
    vector<string> result = mySolution.letterCombinations("23");
    for (int i = 0; i < result.size(); i++)
        cout << result[i] << endl;

 //   cout << "-----------------Test 2--------------------" << endl;


 //   cout << "-----------------Test 3--------------------" << endl;


//    cout << "-----------------Test 4--------------------" << endl;


 //   cout << "-----------------Test 5--------------------" << endl;



}
